package 五月打卡;

/*
 * @author  YxinMiracle
 * @date  2022-05-01 12:10
 * @Gitee: https://gitee.com/yxinmiracle
 */

public class 在排序数组中查找元素的第一个和最后一个位置 {

    public int[] searchRange(int[] nums, int target) {
        // 开始位置：第一个大于等于target的下标
        // 结束位置：最后一个小于等于target下标
        int[] result = new int[2];
        // 先计算开始位置
        int left = 0, right = nums.length; // 会存在找不到的情况
        while (left < right) {
            int min = (left + right) >> 1;
            if (nums[min] >= target) {
                right = min;
            } else {
                left = min + 1;
            }
        }
        if (right == nums.length){
            result[0] = -1;
        }else {
            if (nums[right] == target){
                result[0] = right;
            }else {
                result[0] = -1;
            }
        }

        left = -1;
        right = nums.length - 1;
        while (left < right) {
            int min = (left + right + 1) >> 1; // 防止死循环
            if (nums[min] <= target) {
                left = min;
            } else {
                right = min - 1;
            }
        }
        if (left == -1){
            result[1] = -1;
        }else {
            if (nums[left] == target){
                result[1] = left;
            }else {
                result[1] = -1;
            }
        }
        return result;
    }

}
